package com.lfg.leetcode.leetcode100;


import com.lfg.leetcode.leetcode0.ListNode;

public class No143reorderList {

    public static void main(String[] args) {
        ListNode list = ListNode.deserialize("[1,2,3,4,5,6,7]");
        reorderList(list);
        System.out.println(list.val);
    }

    public static void reorderList(ListNode head) {
        if (null == head) {
            return;
        }
        ListNode node = head;
        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
        }
        if(length == 1){
            return;
        }
        int mid = length / 2;
        ListNode midNode = head;
        for (int i = 0; i < mid - 1; i++) {
            midNode = midNode.next;
        }
        ListNode last = midNode;
        midNode = midNode.next;
        last.next = null;

        ListNode newNode = midNode;
        ListNode nextNode = midNode.next;

        while (null != nextNode) {
            node = nextNode.next;
            nextNode.next = newNode;
            newNode = nextNode;
            nextNode = node;
        }
        midNode.next = null;

        ListNode list1 = head.next;
        ListNode list2 = newNode;

        ListNode ret = head;
        node = head;

        for (int i = 1; i < length; i++) {
            if ((i & 1) == 0) {
                if(null == list1){
                    break;
                }
                node.next = list1;
                node = list1;
                list1 = list1.next;
            } else {
                if(null == list2){
                    break;
                }
                node.next = list2;
                node = list2;
                list2 = list2.next;
            }
        }


        head = ret;

//        ListNode[] list = new ListNode[length];
//        node = head;
//        int index = 0;
//        while (node != null) {
//            list[index++] = node;
//            node = node.next;
//        }
//        node = head;
//        int startIndex = 1;
//        int endIndex = length - 1;
//        while (startIndex <= endIndex) {
//            node.next = list[endIndex--];
//            node = node.next;
//            if (startIndex > endIndex) {
//                break;
//            }
//            node.next = list[startIndex++];
//            node = node.next;
//        }
//        node.next = null;
//    }
    }
}
